home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Frameworks / Disinfectant 2.4 / Notes / Scan Alg next >
Encoding:
Text File  |  1989-06-09  |  6.1 KB  |  140 lines  |  [TEXT/EDIT]
  1. In Tech Note #68, "Searching All Directories on an HFS Volume", Apple 
  2. gives a very simple algorithm for disk scanning.  There's a problem with
  3. this algorithm, however, which I discovered while working on my anti-virus 
  4. program Disinfectant.  I've come up with an improved algorithm that 
  5. solves the problem.  The new algorithm will be part of Disinfectant version
  6. 1.1, which we hope to release early next week.
  7.  
  8. I've wanted to "publish" this new algorithm so that everyone can
  9. benefit from it.  comp.sys.mac.programmer seems as good a place as any!
  10.  
  11. Please understand that this problem is not a "bug" in Disinfectant 1.0,
  12. despite what MacWeek has to say :-)  The "bug" is shared by any program
  13. which uses the TN 68 algorithm to do disk scanning, which I suspect is all
  14. programs which do disk scanning.
  15.  
  16. The basic idea outlined in Tech Note #68 is to make indexed calls to the
  17. PBGetCatInfo file manager routine.  We'll use (abuse) the following
  18. notation for these calls:
  19.  
  20.    r = PBGetCatInfo(d, i, o)
  21.    
  22. means "call PBGetCatInfo to get the i'th object o in directory d, with
  23. result code r."  Note that r will be non-zero if there are no more objects 
  24. in the directory.
  25.  
  26. The algorithm in TN 68, expressed in pseudo-c and stripped of all the
  27. bells and whistles, is as follows:
  28.  
  29.    i = 1
  30.    while (true) {
  31.       if (PBGetCatInfo(d, i, o)) break
  32.       if o is a subdirectory call ourselves recursively to scan o
  33.       if o is a file scan it
  34.       i++
  35.    }
  36.    
  37. This algorithm seems quite simple and fool-proof at first glance, but it
  38. only works if you assume that no other users or tasks are creating or
  39. deleting files or directories while the scan is in progress.
  40.  
  41. As an extreme example, suppose we're scanning a server volume that contains
  42. two files named A and B and a directory C that contains another 1000 files.
  43. Suppose that while we're scanning file B some other user deletes file A.
  44. Our index i in the above algorithm is 2 while we're scanning file B.  When
  45. we finish scanning file B we increment i to 3 and loop, calling
  46. PBGetCatInfo to get the third object in the directory.  But there are
  47. now only two objects in the directory (B and C), so the PBGetCatInfo call
  48. returns a non-zero result code and we break out of the loop and quit.  The
  49. net result is that we end up scanning only 2 out of the 1002 total files
  50. on the server!
  51.  
  52. This problem is most serious when scanning server volumes, where the 
  53. probability of other users creating or deleting objects is often
  54. significant.  The problem can also occur on local volumes under MultiFinder
  55. if other tasks are creating or deleting objects during a scan, or if our
  56. program itself creates or deletes objects on the volume during the scan.
  57. (Disinfectant 1.0 suffers from all three problems, but only the server
  58. problem is really serious.)
  59.  
  60. My solution is quite simple.  I simply recall PBGetCatInfo immediately
  61. after scanning an object to see if it has changed its position in the
  62. directory.  If the position has changed, I rescan the directory to attempt
  63. to locate the new position.
  64.  
  65. The revised algorithm is:
  66.  
  67.    i = 1
  68.    while (true) {      
  69.       if (PBGetCatInfo(d, i, o)) break
  70.       if o is a subdirectory call ourselves recursively to scan o
  71.       if o is a file scan it
  72.       n = the name of object o
  73.       if (!PBGetCatInfo(d, i, o)) {  /* recall PBGetCatInfo */
  74.          m = the name of object o
  75.          if (n == m) {              /* usual case - no position change */
  76.             i++                     /* continue scan with next object */
  77.             continue
  78.          }
  79.       }
  80.       oldi = i                     /* save our old location */
  81.       i = 1                        /* start looking for our new location */
  82.       while (true) {
  83.          if (PBGetCatInfo(d, i, o)) {
  84.             i = oldi               /* just in case we've been deleted in
  85.             break                  /* the last few milliseconds */
  86.          }
  87.          m = the name of object o
  88.          if (n == m) {             /* found new location */
  89.             i++                    /* continue scan with next object */
  90.             break
  91.          }
  92.          i++
  93.       }
  94.    }
  95.  
  96. There is still an unavoidable window in this algorithm where our 
  97. PBGetCatInfo indices can get out of synch with reality, but it is now
  98. only milliseconds wide instead of seconds or even minutes wide.  So the
  99. new algorithm is still not perfect, but it's orders of magnitude better than
  100. the old naive one.
  101.  
  102. In my first attempt to design this new algorithm I tried to be fancy -
  103. I didn't rescan from the beginning of the directory, but I instead tried
  104. to scan backwards or forwards from the current position.  This technique
  105. was slightly faster, but assumed that the directory was maintained in 
  106. alphabetical order using the RelString toolbox routine with caseSens=false
  107. and diacSens=true.  This works OK on normal volumes, but with foreign file
  108. systems and in other "non-standard" cases we can't assume that directories
  109. are in any particular order.  The final algorithm presented above does
  110. not depend on directories being maintained in any particular order.
  111.  
  112. Please note that my new algorithm hasn't yet been put to the acid test
  113. of use by millions of real live users.  But I think it's reasonable and
  114. it has worked just fine in my tests.  Apple, of course, knows nothing
  115. about all this.  If they did they'd probably tell me that it would break
  116. in system 7.0 :-)  So use it at your own risk, etc., etc.
  117.  
  118. It's interesting that this problem is not shared by UNIX and other operating
  119. systems.  In UNIX once an entry is made in a directory its position never
  120. changes.  When entries are deleted they're simply marked "unused".  The
  121. system does not attempt to move all the following entries down to close up
  122. the hole.  There is no attempt made to keep the directories in any 
  123. particular order.
  124.  
  125. The new algorithm is part of the reusable module scan.c, which is part
  126. of the "public" source code of Disinfectant.  Write to me at the address
  127. below if you'd like a copy.
  128.  
  129. Please excuse the length of this posting.  I thought this was a nifty
  130. trick, and there might be others who will find it useful.
  131.  
  132. John Norstad
  133. Academic Computing and Network Services
  134. Northwestern University
  135.  
  136. Bitnet:      jln@nuacc
  137. Internet:    jln@acns.nwu.edu
  138. AppleLink:   a0173
  139. CompuServe:  76666,573
  140.